package LeetCode.linkednode;

public class NC_23 {
    public ListNode nc(ListNode head,int data){
        ListNode frontS = null;
        ListNode frontE = null;
        ListNode backS = null;
        ListNode backE = null;
        ListNode cur = head;
        while (cur != null){
            if(cur.val < data){
                if(frontS == null){
                    frontS = cur;
                    frontE = cur;
                } else {
                    frontE.next = cur;
                    frontE = frontE.next;
                }
            } else {
                if(backS == null){
                    backS = cur;
                    backE = cur;
                } else {
                    backE.next = cur;
                    backE = backE.next;
                }
            }
            cur = cur.next;
        }
        if(frontS == null) {  // 如果没有小于data的部分
            return backS;
        }
        frontE.next = backS;
        if(backS != null) {  // 如果没有大于data的部分
            backE.next = null;
        }
            // if(backS == null) {
            //  return head;
            // }
            // else {
            //  backE.next = null;
            // }


        return frontS;
    }
}
